Wavelet-based compression of images for storage and transmission involving hierarchical subband decomposition is an attractive way for achieving needed computational and coding efficiency. A desirable property of compression schemes is that if the compressed bit stream is truncated at an arbitrary point, the bit stream contains a lower rate representation of the image. Consequently, bits are transmitted in the order of importance. This embedded property can be applied, for example, to budget a fixed number of bits per frame, such as in constant frame-rate synchronous bit rate video communications. It further allows coding to be terminated when a given distortion metric is met, as in archiving images.
One of the prior art approaches for compressing the wavelet coefficient array by exploiting its statistical properties, is a process known as set partitioning in hierarchical trees (hereinafter, “SPIHT”). The process is described in U.S. Pat. No. 5,764,807 to Pearlman et. al., issued June, 1998. SPIHT in turn is a refinement of a process known as Embedded Zerotree Wavelet (“EZW”) which is described in U.S. Pat. No. 5,315,670 to Shapiro, issued June 1994.
These patents to the extent relevant are hereby incorporated by reference. By structuring the data in hierarchical tree sets that are likely to be highly correlated, the EZW process exploits the self-similarity of the wavelet transform at different scales. Pearlman et. al. teaches the further partitioning of the data into lists, to gain additional compression.
More specifically, the scheme of U.S. Pat. No. 5,764,807 requires partitioning the wavelet coefficients into a number of lists, with list membership changing as the execution proceeds, and in some cases involving dual membership of a coefficient in different lists. The constantly changing list memberships are difficult and expensive to maintain. Direct implementation of the process unavoidably requires an inner loop of execution that involves the steps “read value and list membership information, compute significance information, derive and output encoding bits, and modify and save new list membership information”. The memory to preserve list membership information, the instructions to compute new list membership information, and I/O traffic (bandwidth) to save and retrieve that information, all contribute to process overhead and execution time.
With the above-described protocol, the execution speed of the processing on available DRAM hardware is slow. Implementing the SPIHT process in the manner described in U.S. Pat. No. 5,764,807 for HDTV-rate compression for example, requires memory access rates that are close to the limits of currently available commercial DRAM devices.
Therefore, a need exists for a compression scheme which can execute faster, thus accommodating the size and rate of available memory technology, and yet achieve the SPIHT level of performance.